//: [Previous](@previous)
/*:
 [435] 无重叠区间 (区间问题 Medium)
 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

 注意:

 可以认为区间的终点总是大于它的起点。
 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

 ```
 输入: [ [1,2], [2,3], [3,4], [1,3] ]
 输出: 1
 解释: 移除 [1,3] 后，剩下的区间没有重叠。
 ```

 求最少的移除区间个数，等价于尽量多保留不重叠的区间。在选择要保留区间时，区间的结 尾十分重要:选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因 此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。
 */
import Foundation

func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
    let sortIntervals = intervals.sorted(by: { $0[1] < $1[1] })

    var remove = 0
    var prefix = sortIntervals[0][1]
    for i in 1..<sortIntervals.count {
        if sortIntervals[i][0] < prefix {
            remove += 1
        } else {
            prefix = sortIntervals[i][1]
        }
    }

    return remove
}

print(eraseOverlapIntervals([[1,2], [2,3], [3,4], [1,3]]))

//: [Next](@next)
